package com.guaoran.algorithm.binary.tree.order;

import com.guaoran.algorithm.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Auth gucheng
 * @Desc 二叉树有序遍历 中序遍历 ： 左 - 根 - 右
 * https://leetcode.com/problems/binary-tree-inorder-traversal/
 * @Date 2021/1/19 上午11:51
 */
public class InOrderTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode right = new TreeNode(2);
        right.left = new TreeNode(3);
        root.right = right;
        System.out.println(inOrderTraversalDemo(root));
        System.out.println(inOrderTraversal(root));

    }

    private static List<Integer> inOrderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()){
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }

    /**
     * 递归方法
     * @param root
     * @return
     */
    public static List<Integer> inOrderTraversalDemo(TreeNode root) {
        List<Integer> result = new ArrayList();
        if(root == null){
            return result;
        }

        List<Integer> left = inOrderTraversalDemo(root.left);
        List<Integer> right = inOrderTraversalDemo(root.right);

        result.addAll(left);
        result.add(root.val);
        result.addAll(right);
        return result;
    }
}
